package third

/*
	定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

	示例:

	MinStack minStack = new MinStack();
	minStack.push(-2);
	minStack.push(0);
	minStack.push(-3);
	minStack.min();   --> 返回 -3.
	minStack.pop();
	minStack.top();      --> 返回 0.
	minStack.min();   --> 返回 -2.

	提示：

	各函数的调用总次数不超过 20000 次

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
type MinStack struct {
	/*
		给定一个辅助的栈as、栈中只保存最小值、对于该栈
		push时：如果as为空或者要入栈的元素不大于as栈顶元素、as同步入栈
		pop时：如果要出栈的元素与as栈顶元素相同、as同步出栈
	*/
	Stacks          []int
	AssistantStacks []int
}

/** initialize your data structure here. */
func Constructor() MinStack {
	return MinStack{
		Stacks:          make([]int, 0),
		AssistantStacks: make([]int, 0),
	}
}

func (this *MinStack) Push(x int) {
	this.Stacks = append(this.Stacks, x)
	if len(this.AssistantStacks) == 0 || this.AssistantStacks[len(this.AssistantStacks)-1] >= x {
		this.AssistantStacks = append(this.AssistantStacks, x)
	}
}

func (this *MinStack) Pop() {
	top := this.Stacks[len(this.Stacks)-1]
	atop := this.AssistantStacks[len(this.AssistantStacks)-1]
	if top == atop {
		this.AssistantStacks = this.AssistantStacks[:len(this.AssistantStacks)-1]
	}
	this.Stacks = this.Stacks[:len(this.Stacks)-1]
}

func (this *MinStack) Top() int {
	return this.Stacks[len(this.Stacks)-1]
}

func (this *MinStack) Min() int {
	return this.AssistantStacks[len(this.AssistantStacks)-1]
}

/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.Min();
 */
